<!DOCTYPE html><html class="theme-next pisces use-motion" lang="zh-Hans"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1"><meta name="theme-color" content="#222"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css"><link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Damion:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css"><link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css"><link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css"><link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.ico?v=5.1.4"><link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.ico?v=5.1.4"><link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.ico?v=5.1.4"><link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222"><meta name="keywords" content="数据结构,队列,"><link rel="alternate" href="/atom.xml" title="Choice's Blog" type="application/atom+xml"><meta name="description" content="什么是队列(queue)队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，在具体应用中通常用链表或者数组来实现。和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只"><meta name="keywords" content="数据结构,队列"><meta property="og:type" content="article"><meta property="og:title" content="数据结构之队列"><meta property="og:url" content="http://blog.onlinetool.com.cn/dataStructure/dataStructure-queue/index.html"><meta property="og:site_name" content="Choice&#39;s Blog"><meta property="og:description" content="什么是队列(queue)队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，在具体应用中通常用链表或者数组来实现。和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只"><meta property="og:locale" content="zh-Hans"><meta property="og:updated_time" content="2020-09-25T03:37:14.685Z"><meta name="twitter:card" content="summary"><meta name="twitter:title" content="数据结构之队列"><meta name="twitter:description" content="什么是队列(queue)队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，在具体应用中通常用链表或者数组来实现。和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只"><script type="text/javascript" id="hexo.configurations">var NexT=window.NexT||{},CONFIG={root:"/",scheme:"Pisces",version:"5.1.4",sidebar:{position:"left",display:"post",offset:12,b2t:!1,scrollpercent:!1,onmobile:!1},fancybox:!0,tabs:!0,motion:{enable:!0,async:!1,transition:{post_block:"fadeIn",post_header:"slideDownIn",post_body:"slideDownIn",coll_header:"slideLeftIn",sidebar:"slideUpIn"}},duoshuo:{userId:"0",author:"博主"},algolia:{applicationID:"",apiKey:"",indexName:"",hits:{per_page:10},labels:{input_placeholder:"Search for Posts",hits_empty:"We didn't find any results for the search: ${query}",hits_stats:"${hits} results found in ${time} ms"}}}</script><link rel="canonical" href="http://blog.onlinetool.com.cn/dataStructure/dataStructure-queue/"><title>数据结构之队列 | Choice's Blog</title><script type="text/javascript">var _hmt=_hmt||[];!function(){var e=document.createElement("script");e.src="https://hm.baidu.com/hm.js?90aa63e8cd3863bfdba1f3fdfcd619c1";var t=document.getElementsByTagName("script")[0];t.parentNode.insertBefore(e,t)}()</script></head><body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-Hans"><div class="container sidebar-position-left page-post-detail"><div class="headband"> <a href="https://github.com/ch0ice" class="github-corner" aria-label="View source on Github" rel="external nofollow noopener noreferrer" target="_blank"><svg width="80" height="80" viewbox="0 0 250 250" style="fill:#151513;color:#fff;position:absolute;top:0;border:0;right:0" aria-hidden="true"><path d="M0 0 115 115 130 115 142 142 250 250 250 0Z"/><path d="M128.3 109C113.8 99.7 119 89.6 119 89.6 122 82.7 120.5 78.6 120.5 78.6 119.2 72 123.4 76.3 123.4 76.3 127.3 80.9 125.5 87.3 125.5 87.3 122.9 97.6 130.6 101.9 134.4 103.2" fill="currentColor" style="transform-origin:130px 106px" class="octo-arm"/><path d="M115 115C114.9 115.1 118.7 116.5 119.8 115.4L133.7 101.6C136.9 99.2 139.9 98.4 142.2 98.6 133.8 88 127.5 74.4 143.8 58 148.5 53.4 154 51.2 159.7 51 160.3 49.4 163.2 43.6 171.4 40.1 171.4 40.1 176.1 42.5 178.8 56.2 183.1 58.6 187.2 61.8 190.9 65.4 194.5 69 197.7 73.2 200.1 77.6 213.8 80.2 216.3 84.9 216.3 84.9 212.7 93.1 206.9 96 205.4 96.6 205.1 102.4 203 107.8 198.3 112.5 181.9 128.9 168.3 122.5 157.7 114.1 157.9 116.9 156.7 120.9 152.7 124.9L141 136.5C139.8 137.7 141.6 141.9 141.8 141.8Z" fill="currentColor" class="octo-body"/></svg></a><style>.github-corner:hover .octo-arm{animation:octocat-wave 560ms ease-in-out}@keyframes octocat-wave{0%,100%{transform:rotate(0)}20%,60%{transform:rotate(-25deg)}40%,80%{transform:rotate(10deg)}}@media (max-width:500px){.github-corner:hover .octo-arm{animation:none}.github-corner .octo-arm{animation:octocat-wave 560ms ease-in-out}}</style></div><header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="header-inner"><div class="site-brand-wrapper"><div class="site-meta"><div class="custom-logo-site-title"><a href="/" class="brand" rel="start"><span class="logo-line-before"><i></i></span> <span class="site-title">Choice's Blog</span><span class="logo-line-after"><i></i></span></a></div><h1 class="site-subtitle" itemprop="description"></h1></div><div class="site-nav-toggle"> <button><span class="btn-bar"></span><span class="btn-bar"></span><span class="btn-bar"></span></button></div></div><nav class="site-nav"><ul id="menu" class="menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i><br> 首页</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i><br> 关于</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i><br> 标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i><br> 分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i><br> 归档</a></li><li class="menu-item menu-item-sitemap"><a href="/sitemap.xml" rel="section"><i class="menu-item-icon fa fa-fw fa-sitemap"></i><br> 站点地图</a></li><li class="menu-item menu-item-search"><a href="javascript:;" class="popup-trigger"><i class="menu-item-icon fa fa-search fa-fw"></i><br> 搜索</a></li></ul><div class="site-search"><div class="popup search-popup local-search-popup"><div class="local-search-header clearfix"><span class="search-icon"><i class="fa fa-search"></i></span><span class="popup-btn-close"><i class="fa fa-times-circle"></i></span><div class="local-search-input-wrapper"> <input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input"></div></div><div id="local-search-result"></div></div></div></nav></div></header><main id="main" class="main"><div class="main-inner"><div class="content-wrap"><div id="content" class="content"><div id="posts" class="posts-expand"><article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article"><div class="post-block"><link itemprop="mainEntityOfPage" href="http://blog.onlinetool.com.cn/dataStructure/dataStructure-queue/"><span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person"><meta itemprop="name" content="Choice"><meta itemprop="description" content=""><meta itemprop="image" content="/uploads/portrait.png"></span><span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Choice's Blog"></span><header class="post-header"><h2 class="post-title" itemprop="name headline">数据结构之队列</h2><div class="post-meta"><span class="post-time"><span class="post-meta-item-icon"><i class="fa fa-calendar-o"></i></span> <span class="post-meta-item-text">发表于</span> <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-08-07T18:37:39+08:00">2018-08-07</time> <span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-calendar-check-o"></i></span> <span class="post-meta-item-text">更新于&#58;</span> <time title="更新于" itemprop="dateModified" datetime="2020-09-25T11:37:14+08:00">2020-09-25</time></span> <span class="post-category"><span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-folder-o"></i></span> <span class="post-meta-item-text">分类于</span> <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/数据结构/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a></span></span> <span class="post-comments-count"><span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-comment-o"></i></span><a href="/dataStructure/dataStructure-queue/#comments" itemprop="discussionUrl"><span class="post-comments-count valine-comment-count" data-xid="/dataStructure/dataStructure-queue/" itemprop="commentCount"></span></a></span><div class="post-wordcount"><span class="post-meta-item-icon"><i class="fa fa-file-word-o"></i></span> <span class="post-meta-item-text">字数统计&#58;</span> <span title="字数统计">3,245</span> <span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-clock-o"></i></span> <span class="post-meta-item-text">阅读时长 &asymp;</span> <span title="阅读时长">15</span></div></div></header><div class="post-body" itemprop="articleBody"><h3 id="什么是队列-queue"><a href="#什么是队列-queue" class="headerlink" title="什么是队列(queue)"></a>什么是队列(queue)</h3><p>队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，在具体应用中通常用链表或者数组来实现。<br>和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。<br>队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。<br>因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出<font color="#0099ff">（FIFO—first in first out）</font><br><a href="https://github.com/ch0ice/blog-example/tree/master/data-structure/queue/" rel="external nofollow noopener noreferrer" target="_blank"><font color="#0099ff">点击这里查看博客对应的完整代码</font></a></p><h3 id="非循环队列（普通队列）"><a href="#非循环队列（普通队列）" class="headerlink" title="非循环队列（普通队列）"></a>非循环队列（普通队列）</h3><p>非循环队列是最简单的队列，使用动态数组/数组实现，大小是固定的，虽然使用数组作为队列的存储结构，但是在队列中只操作头尾节点，所以插入（入队）和查找（出队）都很快。<br>非循环队列的缺点是可能会出现”假溢出”的情况。<br>下面是一个非循环队列的实现。<br></p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_QSIZE 5 <span class="comment">// 最大队列长度</span></span></span><br><span class="line"><span class="comment">// 队列的数据类型</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Q_Data;</span><br><span class="line"><span class="comment">// 队列的存储结构</span></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Queue</span> &#123;</span></span><br><span class="line">    Q_Data Array[MAX_QSIZE]; <span class="comment">// 阵列空间大小</span></span><br><span class="line">    <span class="keyword">int</span> front; <span class="comment">// 队头</span></span><br><span class="line">    <span class="keyword">int</span> rear; <span class="comment">// 队尾</span></span><br><span class="line">    <span class="keyword">int</span> length; <span class="comment">// 队列长度</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 构造一个空队列Q</span></span><br><span class="line"><span class="function">Queue* <span class="title">Q_Init</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    Queue *Q = (Queue*)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(Queue));</span><br><span class="line">    <span class="keyword">if</span> (!Q)&#123;</span><br><span class="line">        <span class="comment">// 存储分配失败</span></span><br><span class="line">        <span class="built_in">exit</span>(OVERFLOW);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//初始化</span></span><br><span class="line">    Q-&gt;front = Q-&gt;rear = Q-&gt;length = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> Q;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 将Q清为空队列</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Clear</span><span class="params">(Queue *Q)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//清除头尾下标和长度</span></span><br><span class="line">    Q-&gt;front = Q-&gt;rear = Q-&gt;length = <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 入列</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Put</span><span class="params">(Queue *Q, Q_Data x)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//如果当前元素数量等于最大数量 返回 -1</span></span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;rear == MAX_QSIZE)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    Q-&gt;Array[Q-&gt;rear] = x;</span><br><span class="line">    Q-&gt;rear++;</span><br><span class="line">    <span class="comment">//length + 1</span></span><br><span class="line">    Q-&gt;length++;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 出列</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Poll</span><span class="params">(Queue *Q,Q_Data &amp;e)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//如果当前元素数量等于最大数量 返回 -1</span></span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;front == MAX_QSIZE)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    e = Q-&gt;Array[Q-&gt;front];</span><br><span class="line">    Q-&gt;front++;</span><br><span class="line">    <span class="comment">// 移出后減少1</span></span><br><span class="line">    Q-&gt;length--;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p></p><h3 id="循环队列"><a href="#循环队列" class="headerlink" title="循环队列"></a>循环队列</h3><blockquote><p>循环队列可以更简单防止”假溢出”的发生，但队列大小是固定的，使用动态数组/数组实现，相对单链队列来说，插入（入队）和查找（出队）都很快。<br>这里说的循环是逻辑上的循环，体现在入队（put）出队（poll）的操作上面，比如长度是10，队列的头尾指针会始终在0 ～ 9之间循环，也就永远不会出现溢出的情况，因此称为循环队列。<br>循环队列中的循环是以舍弃队列中一个元素空间来达成的，也就是循环队列最大能存储maxSize - 1个元素，比如最大长度是10，那么只能保存9个元素到队列中。<br>下面是一个循环队列的实现。<br></p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 队列的顺序存储结构(循环队列)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_QSIZE 6 <span class="comment">// 最大队列长度+1</span></span></span><br><span class="line"><span class="comment">// 队列的数据类型</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Q_Data;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">    Q_Data *data; <span class="comment">// 初始化的动态分配存储空间</span></span><br><span class="line">    <span class="keyword">int</span> front; <span class="comment">// 头指针，若队列不空，指向队列头元素</span></span><br><span class="line">    <span class="keyword">int</span> rear; <span class="comment">// 尾指针，若队列不空，指向队列尾元素的下一个位置</span></span><br><span class="line">&#125; SqQueue;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 构造一个空队列Q</span></span><br><span class="line"><span class="function">SqQueue* <span class="title">Q_Init</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    SqQueue *Q = (SqQueue*)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(SqQueue));</span><br><span class="line">    <span class="comment">// 存储分配失败</span></span><br><span class="line">    <span class="keyword">if</span> (!Q)&#123;</span><br><span class="line">        <span class="built_in">exit</span>(OVERFLOW);</span><br><span class="line">    &#125;</span><br><span class="line">    Q-&gt;data = (Q_Data *)<span class="built_in">malloc</span>(MAX_QSIZE * <span class="keyword">sizeof</span>(Q_Data));</span><br><span class="line">    <span class="comment">// 存储分配失败</span></span><br><span class="line">    <span class="keyword">if</span> (!Q-&gt;data)&#123;</span><br><span class="line">        <span class="built_in">exit</span>(OVERFLOW);</span><br><span class="line">    &#125;</span><br><span class="line">    Q-&gt;front = Q-&gt;rear = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> Q;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 销毁队列Q，Q不再存在</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Destroy</span><span class="params">(SqQueue *Q)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;data)</span><br><span class="line">        <span class="built_in">free</span>(Q-&gt;data);</span><br><span class="line">    Q-&gt;data = <span class="literal">NULL</span>;</span><br><span class="line">    Q-&gt;front = Q-&gt;rear = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">free</span>(Q);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 将Q清为空队列</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Clear</span><span class="params">(SqQueue *Q)</span> </span>&#123;</span><br><span class="line">    Q-&gt;front = Q-&gt;rear = <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 若队列Q为空队列，则返回1；否则返回-1</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Empty</span><span class="params">(SqQueue Q)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (Q.front == Q.rear) <span class="comment">// 队列空的标志</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 返回Q的元素个数，即队列的长度</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Length</span><span class="params">(SqQueue Q)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_GetHead</span><span class="params">(SqQueue Q, Q_Data &amp;e)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (Q.front == Q.rear) <span class="comment">// 队列空</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    e = Q.data[Q.front];</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 打印队列中的内容</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Print</span><span class="params">(SqQueue Q)</span> </span>&#123;</span><br><span class="line">    Q_Data p = Q.front % MAX_QSIZE;</span><br><span class="line">    <span class="keyword">while</span> (Q.rear != p) &#123;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; Q.data[p] &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">        p = (p + <span class="number">1</span>) % MAX_QSIZE;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 插入元素e为Q的新的队尾元素</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Put</span><span class="params">(SqQueue *Q, Q_Data e)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> ((Q-&gt;rear + <span class="number">1</span>) % MAX_QSIZE == Q-&gt;front) <span class="comment">// 队列满</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    Q-&gt;data[Q-&gt;rear] = e;</span><br><span class="line">    Q-&gt;rear = (Q-&gt;rear + <span class="number">1</span>) % MAX_QSIZE;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 若队列不空，则删除Q的队头元素，用e返回其值，并返回1；否则返回-1</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Poll</span><span class="params">(SqQueue *Q, Q_Data &amp;e)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;front == Q-&gt;rear) <span class="comment">// 队列空</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    e = Q-&gt;data[Q-&gt;front];</span><br><span class="line">    Q-&gt;front = (Q-&gt;front + <span class="number">1</span>) % MAX_QSIZE;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p></p></blockquote><h3 id="单链队列"><a href="#单链队列" class="headerlink" title="单链队列"></a>单链队列</h3><blockquote><p>单链队列使用链表作为基本数据结构，所以不存在”假溢出”的问题，队列长度也没有限制。<br>但插入和读取的时间代价较高，虽然使用链表实现，但链表的优势（O(1)任意节点插入）在队列中被抹去了，因为链表不允许操纵除头尾节点以外的节点，每次插入都需右移指针。<br>下面是一个单链队列的实现。<br></p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 队列的数据类型</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Q_Data;</span><br><span class="line"><span class="comment">// 定义单链队列的存储结构</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">QNode</span> &#123;</span></span><br><span class="line">    Q_Data data;</span><br><span class="line">    QNode *next;</span><br><span class="line">&#125;QNode,*QNodePtr;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">LinkQueue</span>&#123;</span></span><br><span class="line">    <span class="comment">//队头 队尾 指针</span></span><br><span class="line">    QNodePtr front,rear;</span><br><span class="line">&#125;LinkQueue;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 构造一个空队列Q</span></span><br><span class="line"><span class="function">LinkQueue* <span class="title">Q_Init</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="comment">//申请内存</span></span><br><span class="line">    LinkQueue* Q = (LinkQueue*)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LinkQueue));</span><br><span class="line">    <span class="comment">//如果 Q 为 NULL 说明 内存申请失败，结束程序</span></span><br><span class="line">    <span class="keyword">if</span> (!Q)</span><br><span class="line">        <span class="built_in">exit</span>(OVERFLOW);</span><br><span class="line">    <span class="comment">//初始化头尾节点 指向相同地址</span></span><br><span class="line">    Q-&gt;front = Q-&gt;rear = (QNodePtr)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(QNode));</span><br><span class="line">    <span class="comment">//如果 Q-&gt;front 为 NULL 说明 内存申请失败，结束程序</span></span><br><span class="line">    <span class="keyword">if</span> (!Q-&gt;front)</span><br><span class="line">        <span class="built_in">exit</span>(OVERFLOW);</span><br><span class="line">    Q-&gt;front-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">return</span> Q;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 销毁队列Q(无论空否均可)</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Destroy</span><span class="params">(LinkQueue *Q)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (Q-&gt;front) &#123;</span><br><span class="line">        <span class="comment">//将队尾指向队头下一个节点的地址（第1个节点）</span></span><br><span class="line">        Q-&gt;rear = Q-&gt;front-&gt;next;</span><br><span class="line">        <span class="comment">//回收队头</span></span><br><span class="line">        <span class="built_in">free</span>(Q-&gt;front);</span><br><span class="line">        <span class="comment">//将队头指向队尾（相当于第1个节点变成了队头，然后依次第2个第3个、、、</span></span><br><span class="line">        <span class="comment">//直到没有下一个节点，也就是 Q-&gt;front == NULL 的时候）</span></span><br><span class="line">        Q-&gt;front = Q-&gt;rear;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">free</span>(Q);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 将Q清为空队列</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Clear</span><span class="params">(LinkQueue *Q)</span> </span>&#123;</span><br><span class="line">    QNodePtr p, q;</span><br><span class="line">    <span class="comment">//将队尾指向队头点的地址</span></span><br><span class="line">    Q-&gt;rear = Q-&gt;front;</span><br><span class="line">    <span class="comment">//取出第1个节点</span></span><br><span class="line">    p = Q-&gt;front-&gt;next;</span><br><span class="line">    <span class="comment">//回收第1个节点</span></span><br><span class="line">    Q-&gt;front-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">while</span> (p) &#123;</span><br><span class="line">        <span class="comment">//将 q 指向 p（第1个节点）</span></span><br><span class="line">        q = p;</span><br><span class="line">        <span class="comment">//将 p 指向 第2个节点</span></span><br><span class="line">        p = p-&gt;next;</span><br><span class="line">        <span class="comment">//回收第2个节点</span></span><br><span class="line">        <span class="built_in">free</span>(q);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 若Q为空队列，则返回-1，否则返回1</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Empty</span><span class="params">(LinkQueue Q)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (Q.front-&gt;next == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 求队列的长度</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Length</span><span class="params">(LinkQueue Q)</span> </span>&#123;</span><br><span class="line">    Q_Data i = <span class="number">0</span>;</span><br><span class="line">    QNodePtr p;</span><br><span class="line">    p = Q.front;</span><br><span class="line">    <span class="comment">//遍历队列中的节点，直到队尾等于队头</span></span><br><span class="line">    <span class="keyword">while</span> (Q.rear != p) &#123;</span><br><span class="line">        i++;</span><br><span class="line">        p = p-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> i;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 打印队列中的内容</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Print</span><span class="params">(LinkQueue Q)</span> </span>&#123;</span><br><span class="line">    Q_Data i = <span class="number">0</span>;</span><br><span class="line">    QNodePtr p;</span><br><span class="line">    p = Q.front;</span><br><span class="line">    <span class="keyword">while</span> (Q.rear != p) &#123;</span><br><span class="line">        i++;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; p-&gt;next-&gt;data &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">        p = p-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 若队列不空，则用e返回Q的队头元素，并返回1，否则返回-1</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_GetHead</span><span class="params">(LinkQueue Q, Q_Data &amp;e)</span> </span>&#123;</span><br><span class="line">    QNodePtr p;</span><br><span class="line">    <span class="keyword">if</span> (Q.front == Q.rear)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    p = Q.front-&gt;next;</span><br><span class="line">    e = p-&gt;data;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 插入元素e为Q的新的队尾元素</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Q_Put</span><span class="params">(LinkQueue *Q, Q_Data e)</span> </span>&#123;</span><br><span class="line">    QNodePtr p = (QNodePtr)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(QNode));</span><br><span class="line">    <span class="keyword">if</span> (!p) <span class="comment">// 存储分配失败</span></span><br><span class="line">        <span class="built_in">exit</span>(OVERFLOW);</span><br><span class="line">    p-&gt;data = e;</span><br><span class="line">    p-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="comment">//FIFO，将新节点追加到尾节点后面</span></span><br><span class="line">    Q-&gt;rear-&gt;next = p;</span><br><span class="line">    <span class="comment">//将新的节点变成尾节点</span></span><br><span class="line">    Q-&gt;rear = p;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 若队列不空，删除Q的队头元素，用e返回其值，并返回1，否则返回-1</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Poll</span><span class="params">(LinkQueue *Q,Q_Data &amp;e)</span> </span>&#123;</span><br><span class="line">    QNodePtr p;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;front == Q-&gt;rear)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="comment">//取出头节点</span></span><br><span class="line">    p = Q-&gt;front-&gt;next;</span><br><span class="line">    <span class="comment">//取出头节点的数据</span></span><br><span class="line">    e = p-&gt;data;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; e &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    Q-&gt;front-&gt;next = p-&gt;next;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;rear == p)</span><br><span class="line">        Q-&gt;rear = Q-&gt;front;</span><br><span class="line">    <span class="built_in">free</span>(p);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; e &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p></p></blockquote><h3 id="什么是假溢出"><a href="#什么是假溢出" class="headerlink" title="什么是假溢出"></a>什么是假溢出</h3><blockquote><p>假溢出就是系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为”假溢出”。<br>假设我们有一个非循环队列Q，队头指针为Q-&gt;front,队尾指针为Q-&gt;rear,长度为m，队列中元素在向量中的下标从0到m-1。<br>入队Q-&gt;rear++，出队Q-&gt;front++，现在入队m个元素到队列中，此时Q-&gt;front == 0，Q-&gt;rear == m，<br>现在出队m个元素，此时 Q-&gt;front == Q-&gt;rear == m，现在队列中已经没有元素，但此时再做入队操作时，就发生了”假溢出”。<br>下面举个例子<br></p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"初始化非循环队列"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">Queue *Q = Q_Init();</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 0;</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"插入数据（put）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">Q_Put(Q, <span class="number">111</span>);</span><br><span class="line">Q_Put(Q, <span class="number">222</span>);</span><br><span class="line">Q_Put(Q, <span class="number">333</span>);</span><br><span class="line">Q_Put(Q, <span class="number">444</span>);</span><br><span class="line">Q_Put(Q, <span class="number">555</span>);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 5;</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"取出并删除元素（poll）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">Q_Data head_data;</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 5,Q-&gt;rear == 5;队列中没有数据</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"插入数据（put）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">Q_Put(Q, <span class="number">666</span>);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 5,Q-&gt;rear == 5; 没有变化，Q_Put() 会返回 -1，也就是插入失败，这就发生了 "假溢出"</span></span><br></pre></td></tr></table></figure><p></p></blockquote><h3 id="怎么解决假溢出"><a href="#怎么解决假溢出" class="headerlink" title="怎么解决假溢出"></a>怎么解决假溢出</h3><ol><li><p>将队列看成首尾相连即循环队列</p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 循环队列中有两种方法可以判断队空或队满</span></span><br><span class="line"><span class="comment">// 1.“牺牲一个单元”，Q-&gt;front == Q-&gt;rear 时为队空，(Q-&gt;rear + 1) % MAX_QSIZE == Q-&gt;front 时为队满。</span></span><br><span class="line"><span class="comment">// 2.“设标记”，如设标记tag，若出队时发生Q-&gt;front==Q-&gt;rear为队空，tag == 1；若入队时发生Q-&gt;front == Q-&gt;rear为队满，tag == 2。</span></span><br><span class="line"><span class="comment">// 一般来说都是使用第1种方法，下面解析一下第一种方法。</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"初始化循环队列"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">SqQueue *Q = Q_Init();</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 0;</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"插入数据（put）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"><span class="comment">//入队时 Q-&gt;rear = (Q-&gt;rear + 1) % MAX_QSIZE</span></span><br><span class="line">Q_Data front_data;</span><br><span class="line">Q_Put(Q,<span class="number">111</span>);</span><br><span class="line">Q_Put(Q,<span class="number">222</span>);</span><br><span class="line">Q_Put(Q,<span class="number">333</span>);</span><br><span class="line">Q_Put(Q,<span class="number">444</span>);</span><br><span class="line">Q_Put(Q,<span class="number">555</span>);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 5;</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"取出并删除元素（poll）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"><span class="comment">//出队时 Q-&gt;front = (Q-&gt;front + 1) % MAX_QSIZE</span></span><br><span class="line">Q_Data head_data;</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line">Q_Poll(Q,head_data);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 5,Q-&gt;rear == 5;队列中没有数据</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"插入数据（put）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"><span class="comment">//入队时 Q-&gt;rear = (Q-&gt;rear + 1) % MAX_QSIZE</span></span><br><span class="line">Q_Put(Q,<span class="number">666</span>);</span><br><span class="line">Q_Put(Q,<span class="number">777</span>);</span><br><span class="line">Q_Put(Q,<span class="number">888</span>);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 5,Q-&gt;rear == 2;队列三个元素</span></span><br></pre></td></tr></table></figure></li><li><p>出队时将队列所有元素向前“平移”1位</p><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"初始化非循环队列"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">Queue *Q = Q_Init();</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 0;</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"插入数据（put）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">Q_Put(Q, <span class="number">111</span>);</span><br><span class="line">Q_Put(Q, <span class="number">222</span>);</span><br><span class="line">Q_Put(Q, <span class="number">333</span>);</span><br><span class="line">Q_Put(Q, <span class="number">444</span>);</span><br><span class="line">Q_Put(Q, <span class="number">555</span>);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 5;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//将非循环队列出列方法更改为如下</span></span><br><span class="line"><span class="comment">// 出列 解决"假溢出"</span></span><br><span class="line"><span class="function">Q_Data <span class="title">Q_Poll_New</span><span class="params">(Queue *Q,Q_Data &amp;e)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//如果当前元素数量等于最大数量 返回 -1</span></span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;front == <span class="number">0</span> || Q-&gt;front == MAX_QSIZE)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    e = Q-&gt;Array[Q-&gt;front];</span><br><span class="line">    <span class="keyword">int</span> x = MAX_QSIZE;</span><br><span class="line">    <span class="keyword">while</span>(x != <span class="number">0</span>)&#123;</span><br><span class="line">        Q-&gt;Array[x<span class="number">-1</span>] = Q-&gt;Array[x];</span><br><span class="line">        x--;</span><br><span class="line">    &#125;</span><br><span class="line">    Q-&gt;rear--;</span><br><span class="line">    <span class="comment">// 移出后減少1</span></span><br><span class="line">    Q-&gt;length--;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"取出并删除元素（poll）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"><span class="comment">//调用新出列方法</span></span><br><span class="line">Q_Data head_data;</span><br><span class="line">Q_Poll_New(Q,head_data);</span><br><span class="line">Q_Poll_New(Q,head_data);</span><br><span class="line">Q_Poll_New(Q,head_data);</span><br><span class="line">Q_Poll_New(Q,head_data);</span><br><span class="line">Q_Poll_New(Q,head_data);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 0;队列中没有数据</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">cout</span> &lt;&lt; <span class="string">"插入数据（put）"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">Q_Put(Q, <span class="number">666</span>);</span><br><span class="line"><span class="comment">//此时 Q-&gt;front == 0,Q-&gt;rear == 1;队列中1个元素</span></span><br></pre></td></tr></table></figure></li></ol><h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h3><ul><li>非循环队列是最简单的队列，动态数组/数组实现，队列大小是固定，插入（入队）和查找（出队）快，可能会出现”假溢出”的情况。</li><li>动态数组/数组实现，队列大小是固定，插入（入队）和查找（出队）快，不会出现”假溢出”。</li><li>单链队列使用链表实现，不存在”假溢出”的问题，队列长度没有限制，插入和读取的时间代价较高。</li></ul></div><div><div id="wechat_subscriber" style="display:block;padding:10px 0;margin:20px auto;width:100%;text-align:center"> <img id="wechat_subscriber_qcode" src="/uploads/wechat-qcode.jpg" alt="Choice wechat" style="width:200px;max-width:100%"><div>关注公众号，获取文章更新通知。</div></div></div><div><div><div style="text-align:center;color:#ccc;font-size:14px">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div></div></div><div><div style="padding:10px 0;margin:20px auto;width:90%;text-align:center"><div>坚持原创技术分享，您的支持将鼓励我继续创作！</div> <button id="rewardButton" disable="enable" onclick='var qr=document.getElementById("QR");"none"===qr.style.display?qr.style.display="block":qr.style.display="none"'> <span>打赏</span></button><div id="QR" style="display:none"><div id="wechat" style="display:inline-block"> <img id="wechat_qr" src="/uploads/wechatpay.png" alt="Choice 微信支付"><p>微信支付</p></div><div id="alipay" style="display:inline-block"> <img id="alipay_qr" src="/uploads/alipay.png" alt="Choice 支付宝"><p>支付宝</p></div></div></div></div><div><ul class="post-copyright"><li class="post-copyright-author"> <strong>本文作者：</strong> Choice</li><li class="post-copyright-link"> <strong>本文链接：</strong> <a href="http://blog.onlinetool.com.cn/dataStructure/dataStructure-queue/" title="数据结构之队列">http://blog.onlinetool.com.cn/dataStructure/dataStructure-queue/</a></li><li class="post-copyright-license"> <strong>版权声明：</strong> 本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow noopener noreferrer" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！</li></ul></div><footer class="post-footer"><div class="post-tags"> <a href="/tags/数据结构/" rel="tag"># 数据结构</a> <a href="/tags/队列/" rel="tag"># 队列</a></div><div class="post-nav"><div class="post-nav-next post-nav-item"><a href="/dataStructure/dataStructure-vector/" rel="next" title="数据结构之向量"><i class="fa fa-chevron-left"></i> 数据结构之向量</a></div><span class="post-nav-divider"></span><div class="post-nav-prev post-nav-item"> <a href="/developTool/iterm2-ohmyshell/" rel="prev" title="iTerm2 + ohMyZsh 打造Mac完美终端">iTerm2 + ohMyZsh 打造Mac完美终端<i class="fa fa-chevron-right"></i></a></div></div></footer></div></article><div class="post-spread"></div></div></div><div class="comments" id="comments"></div></div><div class="sidebar-toggle"><div class="sidebar-toggle-line-wrap"><span class="sidebar-toggle-line sidebar-toggle-line-first"></span><span class="sidebar-toggle-line sidebar-toggle-line-middle"></span><span class="sidebar-toggle-line sidebar-toggle-line-last"></span></div></div><aside id="sidebar" class="sidebar"><div class="sidebar-inner"><ul class="sidebar-nav motion-element"><li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap"> 文章目录</li><li class="sidebar-nav-overview" data-target="site-overview-wrap"> 站点概览</li></ul><section class="site-overview-wrap sidebar-panel"><div class="site-overview"><div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person"> <img class="site-author-image" itemprop="image" src="/uploads/portrait.png" alt="Choice"><p class="site-author-name" itemprop="name">Choice</p><p class="site-description motion-element" itemprop="description"></p></div><nav class="site-state motion-element"><div class="site-state-item site-state-posts"> <a href="/archives/"><span class="site-state-item-count">15</span> <span class="site-state-item-name">日志</span></a></div><div class="site-state-item site-state-categories"> <a href="/categories/index.html"><span class="site-state-item-count">5</span> <span class="site-state-item-name">分类</span></a></div><div class="site-state-item site-state-tags"> <a href="/tags/index.html"><span class="site-state-item-count">18</span> <span class="site-state-item-name">标签</span></a></div></nav><div class="feed-link motion-element"><a href="/atom.xml" rel="alternate"><i class="fa fa-rss"></i> RSS</a></div><div class="links-of-author motion-element"><span class="links-of-author-item"><a href="https://github.com/ch0ice" target="_blank" title="GitHub" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-github"></i> GitHub</a></span><span class="links-of-author-item"><a href="mailto:liuzeyuan@163.com" target="_blank" title="邮箱" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-envelope"></i> 邮箱</a></span><span class="links-of-author-item"><a href="https://weibo.com/ITwuqing?topnav=1&wvr=6&topsug=1&is_hot=1" target="_blank" title="微博" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-weibo"></i> 微博</a></span><span class="links-of-author-item"><a href="https://www.zhihu.com/people/mr_liuzeyuan/activities" target="_blank" title="知乎" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-book"></i> 知乎</a></span></div></div></section><section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active"><div class="post-toc"><div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#什么是队列-queue"><span class="nav-number">1.</span> <span class="nav-text">什么是队列(queue)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#非循环队列（普通队列）"><span class="nav-number">2.</span> <span class="nav-text">非循环队列（普通队列）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#循环队列"><span class="nav-number">3.</span> <span class="nav-text">循环队列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#单链队列"><span class="nav-number">4.</span> <span class="nav-text">单链队列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#什么是假溢出"><span class="nav-number">5.</span> <span class="nav-text">什么是假溢出</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#怎么解决假溢出"><span class="nav-number">6.</span> <span class="nav-text">怎么解决假溢出</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#总结"><span class="nav-number">7.</span> <span class="nav-text">总结</span></a></li></ol></div></div></section></div></aside></div></main><footer id="footer" class="footer"><div class="footer-inner"><script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div class="copyright">&copy; 2018 &mdash; <span itemprop="copyrightYear">2020</span><span class="with-love" id="animate"><i class="fa fa-heart"></i></span> <span class="author" itemprop="copyrightHolder">Choice</span> <span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-area-chart"></i></span> <span class="post-meta-item-text">Site words total count&#58;</span> <span title="Site words total count">33.4k</span></div><div class="powered-by"><i class="fa fa-user-md"></i> <span id="busuanzi_container_site_uv">本站访客数:<span id="busuanzi_value_site_uv"></span> 次</span></div> <span class="post-meta-divider">|</span><div class="powered-by"> <span id="busuanzi_container_site_pv">本站总访问量:<span id="busuanzi_value_site_pv"></span> 次</span></div></div></footer><div class="back-to-top"><i class="fa fa-arrow-up"></i></div></div><script type="text/javascript">"[object Function]"!==Object.prototype.toString.call(window.Promise)&&(window.Promise=null)</script><script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script><script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script><script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script><script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script><script id="ribbon" type="text/javascript" size="300" alpha="0.6" zindex="-1" src="/lib/canvas-ribbon/canvas-ribbon.js"></script><script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script><script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script><script src="//unpkg.com/valine/dist/Valine.min.js"></script><script type="text/javascript">
    var GUEST = ['nick','mail','link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item=>{
      return GUEST.indexOf(item)>-1;
    });
    new Valine({
        el: '#comments' ,
        verify: false,
        notify: false,
        appId: '9SHSaI9JxokTuIBAUR71UrFK-gzGzoHsz',
        appKey: 'SACKdrI10MKOqjRl0GzdREWg',
        placeholder: 'Just go go',
        avatar:'retro',
        guest_info:guest,
        pageSize:'10' || 10,
    });
  </script><script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script><script>!function(){var t=document.createElement("script"),e=window.location.protocol.split(":")[0];t.src="https"===e?"https://zz.bdstatic.com/linksubmit/push.js":"http://push.zhanzhang.baidu.com/push.js";var s=document.getElementsByTagName("script")[0];s.parentNode.insertBefore(t,s)}()</script></body></html>